package com.zjj.algorithm.learning.atguigu.tree;

/**
 * 线索化二叉树
 *
 * @author zjj_admin
 * @date 2022/11/27 10:05
 */
public class ThreadedBinaryTree extends BinaryTree {

    /**
     * 为了实现线索化，需要创建
     */
    private ThreadedTreeNode pre;

    public ThreadedTreeNode getPre() {
        return pre;
    }


    /**
     *                                 1
     *                           2           3
     *                       4      5      6
     */

    /**
     * 中序线索二叉树
     *
     * @param node
     */
    public void midThreadedNodes(ThreadedTreeNode node) {
        if (node == null) {
            return;
        }

        //1、线索化左子树
        midThreadedNodes((ThreadedTreeNode) node.getLeft());
        //2、线索化当前节点
        //处理当前节点的前驱结点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }

        //处理后继节点
        if (pre != null && pre.getRight() == null) {
            //让前驱结点的右指针指向当前节点
            pre.setRight(node);
            //修改前驱节点的类型
            pre.setRightType(1);
        }
        //每处理结束一个节点，让当前节点是下一个节点的前驱结点
        this.pre = node;

        //3、线索化右子树
        midThreadedNodes((ThreadedTreeNode) node.getRight());
    }


    /**
     * 线索化二叉树的遍历
     */
    @Override
    public void midOrder() {
        ThreadedTreeNode node = (ThreadedTreeNode) this.getRoot();
        while (node != null) {
            //循环找到第一个 leftType= 1 的节点
            while (node.getLeftType() == 0) {
                node = (ThreadedTreeNode) node.getLeft();
            }
            //打印当前这个节点
            System.out.println("node = " + node);
            while (node.getRightType() == 1) {
                node = (ThreadedTreeNode) node.getRight();
                System.out.println("node = " + node);
            }
            //替换这个遍历的节点
            node = (ThreadedTreeNode) node.getRight();
        }
    }

    /**
     * 前序线索二叉树
     * @param node
     */
    public void preThreadedNodes(ThreadedTreeNode node) {

    }
}
